"""
example04 - 二分查找

Author: Administrator
Date: 2024/1/23
"""


def seq_search(items: list, key) -> int:
    """
    顺序查找（渐近时间复杂度0(n)）

    :param items: 待查找的列表
    :param key: 要找的元素
    :return: 找到了返回元素的索引，找不到返回-1
    """
    for index, item in enumerate(items):
        if item == key:
            return index
    return -1


def bin_search(items: list, key) -> int:
    """
    二分查找（渐进时间复杂度O（log2 n））

    :param items: 待查找的列表（元素有序）
    :param key: 要找的元素
    :return: 找到了返回元素的索引，找不到返回-1
    """
    start, end = 0, len(items) - 1
    while start <= end:
        mid = (start + end) // 2
        if key > items[mid]:
            start = mid + 1
        elif key < items[mid]:
            end = mid - 1
        else:
            return mid
    return -1